#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
using namespace std;

/***
 * 1. 拉链法解决哈希冲突
 * 2. 哈希表插入及查找算法
 * 3. 二叉树结构体
 * 4. 二叉排序树, 给定Value 若存在输出比Value大的值中最小的值 若不存在 输出不存在
 * */

// 第一二题
typedef struct HashNode
{
    HashNode *next;
    int key;
    int value;
} HashNode;

typedef struct HashTable
{
    HashNode **table; // 哈希表
    int length;
    int max_size;
} HashTable;

// 初始化哈希表
void InitHashTable(HashTable &H)
{
    H.length = 0;
    H.max_size = 13;
    H.table = (HashNode **)malloc(sizeof(HashNode *) * H.max_size);
    memset(H.table, 0, sizeof(HashNode *) * H.max_size); // 都初始化为空
}

// 新建结点
HashNode *NewHashNode(int key, int value)
{
    HashNode *node = (HashNode *)malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

// 哈希规则
int HashFunc(int key, int size)
{
    return key % size;
}

// 插入
void Insert(HashTable &H, int key, int value)
{
    int index = HashFunc(key, H.max_size);
    HashNode *cur = H.table[index];
    while (cur)
    {
        if (cur->key == key)
        {
            cur->value = value; // 元素已经存在 覆盖
            return;
        }

        cur = cur->next;
    }
    // 头插法插入
    HashNode *node = NewHashNode(key, value);
    node->next = H.table[index];
    H.table[index] = node;
    H.length++;
    return;
}

// 查找
HashNode *Find(HashTable H, int key)
{
    int index = HashFunc(key, H.max_size);
    HashNode *cur = H.table[index];
    while (cur)
    {
        if (cur->key == key)
            return cur;

        cur = cur->next;
    }
    return NULL;
}

// 输出
void Print(HashTable H)
{
    for (int i = 0; i < H.max_size; i++)
    {
        printf("%2d :", i);
        HashNode *cur = H.table[i];
        while (cur)
        {
            printf("(%d, %d)->", cur->key, cur->value);
            cur = cur->next;
        }
        printf("null\n");
    }
}

// 第三四题
typedef struct TNode
{
    int data;
    TNode *left, *right;
} * Tree, TNode;

// 递归
bool FindMinValue(Tree T, int value, int &min)
{
    if (!T)
        return false; // 没找到

    if (T->data == value)
        return true; // 找到了

    bool res;
    if (T->data > value)
        res = FindMinValue(T->left, value, min);
    else
        res = FindMinValue(T->right, value, min);

    if (res)
        min = T->data; // 记录结果 此处只赋值一次 为匹配结点的父结点

    return false;
}

// 非递归
void FindMinValue2(Tree T, int e, int &min)
{
    TNode *cur = T;
    while (!cur)
    {
        if (cur->data > e)
        {
            min = cur->data;
            cur = cur->left;
        }
        else
        {
            cur = cur->right;
        }
    }
}

// 测试用
TNode *NewNode(int e)
{
    TNode *s = (TNode *)malloc(sizeof(TNode));
    s->data = e;
    s->left = NULL;
    s->right = NULL;
    return s;
}

// 层序遍历
void PrintTree(Tree T)
{
    queue<TNode *> q;
    if (T != NULL)
    {
        q.push(T);
    }
    while (!q.empty())
    {
        printf("%d ", q.front()->data);
        if (q.front()->left != NULL)
            q.push(q.front()->left);

        if (q.front()->right != NULL)
            q.push(q.front()->right);
        q.pop();
    }
}

int main()
{
    // 第一题
    HashTable H;
    InitHashTable(H);
    Insert(H, 1, 1);
    Insert(H, 2, 2);
    Insert(H, 14, 2);
    Print(H);
    printf("==========\n");
    HashNode *res = Find(H, 2);
    printf("找到了 (%d, %d) \n", res->key, res->value);

    printf("==========\n");
    Tree T;
    T = NewNode(4);
    T->left = NewNode(3);
    T->right = NewNode(5);
    T->left->left = NewNode(1);
    T->left->right = NewNode(2);
    T->right->left = NewNode(4);

    PrintTree(T);
    printf("\n");
    printf("==========\n");
    int min = 0;
    FindMinValue(T, 3, min);
    printf("找到了 %d \n", min);
    FindMinValue2(T, 3, min);
    printf("找到了 %d \n", min);

    return 0;
}